#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>

using namespace std;

struct Node
{
    int v;
    Node *next;
    Node( ) { next = NULL; }
};

int n, m, cnt, s[ 10001 ], num[ 10001 ], count, c[ 10001 ];
Node *li[ 10001 ], *lif[ 10001 ];
bool visit[ 10001 ];
const int MAXN = 5001;
const int INF = 1 << 28;
int Mx[MAXN], My[MAXN], Nx, Ny;
bool g[MAXN][MAXN];
int dx[MAXN], dy[MAXN], dis;
bool vst[MAXN];
bool searchP(void){
queue<int> Q;
dis = INF;
memset(dx, -1, sizeof(dx));
memset(dy, -1, sizeof(dy));
for (int i = 0; i < Nx; i++)
if (Mx[i] == -1){
Q.push(i); dx[i] = 0;
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
if (dx[u] > dis) break;
for (int v = 0; v < Ny; v++)
if (g[u][v] && dy[v] == -1) {
dy[v] = dx[u]+1;
if (My[v] == -1) dis = dy[v];
else{
dx[My[v]] = dy[v]+1;
Q.push(My[v]);
}
}
}
return dis != INF;
}

bool DFS(int u){
for (int v = 0; v < Ny; v++)
if (!vst[v] && g[u][v] && dy[v] == dx[u]+1) {
vst[v] = 1;
if (My[v] != -1 && dy[v] == dis) continue;
if (My[v] == -1 || DFS(My[v])) {
My[v] = u; Mx[u] = v;
return 1;
}
}
return 0;
}
int MaxMatch(void){
int res = 0;
memset(Mx, -1, sizeof(Mx));
memset(My, -1, sizeof(My));
while (searchP()) {
memset(vst, 0, sizeof(vst));
for (int i = 0; i < Nx; i++)
if (Mx[i] == -1 && DFS(i)) res++;
}
return res;
}

void init( )
{
    int i, a, b;
    Node *p;
    scanf("%d%d", &n, &m);
    for ( i = 0; i < n; i++ )
    {
        li[ i ] = new Node;
        lif[ i ] = new Node;
    }
    while ( m-- )
    {
        scanf("%d%d", &a, &b);
        a--; b--;
        p = li[ a ];
        while ( p->next )
            p = p->next;
        p->next = new Node;
        p->next->v = b;
        p = lif[ b ];
        while ( p->next )
            p = p->next;
        p->next = new Node;
        p->next->v = a;
    }
}

void dfs1( int p )
{
    Node *pos = li[ p ];
    visit[ p ] = true;
    while ( pos->next )
    {
        pos = pos->next;
        if ( !visit[ pos->v ] )
            dfs1( pos->v );
    }
    s[ cnt++ ] = p;
}

void dfs2( int p )
{
    Node *pos = lif[ p ];
    visit[ p ] = true;
    num[ p ] = cnt;
    c[ cnt ]++;
    while ( pos->next )
    {
        pos = pos->next;
        if ( !visit[ pos->v ] )
            dfs2( pos->v );
    }
}

void work( )
{
    int i, j;
    Node *pos;
    for ( i = 0; i < n; i++ )
        visit[ i ] = false;
    cnt = 0;
    for ( i = 0; i < n; i++ )
        if ( !visit[ i ] )
            dfs1( i );
    for ( i = 0; i < n; i++ )
        visit[ i ] = false;
    cnt = 0;
    for ( i = n - 1; i >= 0; i-- )
        if ( !visit[ s[ i ] ] )
        {
            dfs2( s[ i ] );
            cnt++;
        }
    memset( g, 0, sizeof( g ) );
    for ( i = 0; i < n; i++ )
    {
        pos = li[ i ];
        while ( pos->next )
        {
            pos = pos->next;
            if ( num[ i ] != num[ pos->v ] )
                g[ num[ i ] ][ num[ pos->v ] ] = 1;
        }
    }
    Nx = Ny = cnt;
}

void print( )
{/*
    int i, in[ 10001 ], p;
    bool vv[ 10001 ];
    queue<int> q;
    memset( vv, 0, sizeof( vv ) );
    Node *pos;
    for ( i = 0; i < count; i++ )
        in[ i ] = 0;
    for ( i = 0; i < n; i++ )
    {
        pos = li[ i ];
        while ( pos->next )
        {
            pos = pos->next;
            if ( num[ i ] != num[ pos->v ] )
                in[ num[ pos->v ] ]++;
        }
    }
    cnt = 0;
    printf("%d\n", cnt);*/
}

int main( )
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        init( );
        work( );
        printf("%d\n", Nx - MaxMatch());
    }
    return 0;
}
